package com.LeeCode;

import java.util.Collections;
import java.util.List;

/**
 * 最大合金数
 */

public class Code2861 {
    public static void main(String[] args) {

    }

    public int maxNumberOfAlloys(int n, int k, int budget, List<List<Integer>> composition, List<Integer> Stock, List<Integer> Cost) {
        int mx = Collections.min(Stock) + budget;
        Integer[] stock = Stock.toArray(new Integer[Stock.size()]); // 转成数组更快
        Integer[] cost = Cost.toArray(new Integer[Cost.size()]);

        int ans = 0;
        for (List<Integer> Comp : composition) {
            Integer[] comp = Comp.toArray(new Integer[Comp.size()]);
            int left = ans;
            int right = mx + 1;
            while (left + 1 < right) { // 开区间写法
                int mid = (left + right) >>> 1;
                long money = 0;
                for (int i = 0; i < n && money <= budget; i++) {
                    if (stock[i] < (long) comp[i] * mid) {
                        money += ((long) comp[i] * mid - stock[i]) * cost[i];
                    }
                }
                if (money <= budget) {
                    left = mid;
                } else {
                    right = mid;
                }
            }
            ans = left;
        }
        return ans;
    }
}
